package com.lwl.Algorithmic_data_structure.归并排序.mycode;

/**
 * 并归排序的递归与非递归(迭代) 版本
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] array = {
                2,3,4,5,1,8,9,7,6,0
        };

//        mergeSortRecursion(array);
        mergeSortLoop(array);

        for (int i : array) {
            System.out.println(i);
        }
    }

    /**
     * 非递归(迭代)版本的并归排序
     */
    public static void mergeSortLoop(int[] array)
    {
        if (array == null || array.length < 2){
            return;
        }

        int len = array.length;
        //每次进行比较的步长,即每次两两比较的数组长度
        int stepSize = 1;

        while (stepSize < len)
        {
            //当前左数组的第一个位置,与其对应的右数组第一个位置为 left + stepSize（如果没超过数组长度的话）
            int left = 0;

            while (left < len)
            {
                if (left + stepSize >= len){
                    break;
                }
                //左数组最后一位
                int mid = left + stepSize - 1;
                //右数组最后一位，因为有可能加上步长就超过数组长度了
                int right = Math.min(len - 1, mid + stepSize);
                //合并左右数组
                merge(array, left, mid, right);
                //到下一个两两比较的数组中的左数组的第一位
                left = right + 1;
            }
            //防止步长溢出，有些极限例子如果步长直接乘2会导致溢出
            if (stepSize > len / 2)
            {
                break;
            }

            stepSize <<= 1;
        }
    }

    /**
     *  递归版本的并归排序
     */
    public static void mergeSortRecursion(int[] array)
    {
        if(array == null || array.length < 2)
        {
            return;
        }
        process(array, 0, array.length - 1);
    }

    /**
     * 递归调用本身完成数组的排序工作
     */
    private static void process(int[] array, int left, int right)
    {
        if (left >= right){
            return;
        }

        int mid = left + ((right - left) >> 1);

        process(array, left, mid);
        process(array,mid + 1, right);
        //将有序的左右数组合并到原数组当中
        merge(array, left, mid, right);
    }

    /**
     *  将左右数组合并起来，mid为左数组第后一个数字
     */
    private static void merge(int[] array, int left, int mid, int right) {
        //临时数组
        int[] help = new int[right - left + 1];
        //插入临时数组的下标
        int index = 0;
        //左数组下标
        int l = left;
        //右数组下标
        int r = mid + 1;

        while (l <= mid && r <= right){
            if (array[l] <= array[r]){
                help[index++] = array[l++];
            }else{
                help[index++] = array[r++];
            }
        }

        while (l <= mid){
            help[index++] = array[l++];
        }
        while (r <= right){
            help[index++] = array[r++];
        }

        for (int i = 0; i < help.length; i++) {
            array[left + i] = help[i];
        }
    }
}
